'''
Given a 2D board and a word, find if the word exists in the grid.

The word can be constructed from letters of sequentially adjacent cell, where "adjacent" cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once.

Example:

board =
[
  ['A','B','C','E'],
  ['S','F','C','S'],
  ['A','D','E','E']
]

Given word = "ABCCED", return true.
Given word = "SEE", return true.
Given word = "ABCB", return false.
'''

class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        '''
        2020-10-6 李运辰
        明白思路，但不太熟悉
        
        '''
        r = len(board)
        c = len(board[0])
        
        seed = set()
        path = [(0,1),(0,-1),(1,0),(-1,0)]
        
        #从当前元素往下比较
        def helper(i,j,cnt):
            if cnt == len(word):
                return True
            for k in path:
                x = i+k[0]
                y = j+k[1]
                if 0<=x<r and 0<=y<c and (x,y) not in seed and board[x][y]==word[cnt]:
                    seed.add((x,y))
                    if helper(x,y,cnt+1):
                        return True
                    seed.remove((x,y))
            
        
        
        #从左到右，从上到下，遍历每一个元素
        for i in range(r):
            for j in range(c):
                seed.add((i,j))
                if board[i][j] == word[0] and helper(i,j,1):
                    return True
                seed.remove((i,j))
                